package com.wzh.test.graphic;

import java.lang.reflect.Array;
import java.util.*;

/**
 * 利用Kruskal算法解决公交站最短路径问题
 */
public class KruskalDemo {
    public static void main(String[] args) {
        Graphic graphic = new Graphic(7);
        String[] vertex = {"A", "B", "C", "D", "E", "F", "G"};
        for (String element : vertex) {
            graphic.addVertex(element);
        }
        graphic.addEdge("A", "B", 12);
        graphic.addEdge("A", "F", 16);
        graphic.addEdge("A", "G", 14);

        graphic.addEdge("B", "C", 10);
        graphic.addEdge("B", "F", 7);

        graphic.addEdge("C", "D", 3);
        graphic.addEdge("C", "E", 5);
        graphic.addEdge("C", "F", 6);

        graphic.addEdge("D", "E", 4);

        graphic.addEdge("E", "F", 2);
        graphic.addEdge("E", "G", 8);

        graphic.addEdge("F", "G", 9);

        graphic.showGraphic();

        EdgeVertex[] arrEdgeVertex = orderEdge(graphic);

        int[] parent = new int[graphic.vertexList.size()];
        List<EdgeVertex> selectedEdges = new ArrayList<>();
        for (int i = 0; i < arrEdgeVertex.length; i++) {
            if (selectedEdges.size() == 0) {
                selectedEdges.add(arrEdgeVertex[i]);
            } else {
                //添加之前需要找到当前这个节点能够到达的最大顶点
                int m = getRootIndex(parent,arrEdgeVertex[i].beginVertexIndex);
                int n = getRootIndex(parent,arrEdgeVertex[i].endVertexIndex);
                if(m != n){
                    parent[m] = n;
                    selectedEdges.add(arrEdgeVertex[i]);
                }
            }
        }


        System.out.println("最终选中的边");
        for (EdgeVertex selectedEdge : selectedEdges) {
            System.out.println(selectedEdge);
        }
    }

    public static int getRootIndex(int[] parent,int i){
        while (parent[i] != 0){
            i = parent[i];
        }
        return i;
    }


    /**
     * 给你一个图，要求按照edge从小到大进行排序
     *
     * @param graphic
     */
    public static EdgeVertex[] orderEdge(Graphic graphic) {
        List<EdgeVertex> edgeVertexList = new ArrayList<>();
        for (int i = 0; i < graphic.edges.length; i++) {
            for (int j = i + 1; j < graphic.edges[i].length; j++) {
                if (graphic.edges[i][j] > 0) {
                    EdgeVertex edgeVertex = new EdgeVertex();
                    edgeVertex.weight = graphic.edges[i][j];
                    edgeVertex.beginVertexIndex = i;
                    edgeVertex.endVertexIndex = j;
                    edgeVertex.beginVertex = graphic.vertexList.get(i);
                    edgeVertex.endVertex = graphic.vertexList.get(j);

                    edgeVertexList.add(edgeVertex);
                }
            }
        }
        EdgeVertex[] arrEdgeVertex = new EdgeVertex[edgeVertexList.size()];
        edgeVertexList.toArray(arrEdgeVertex);
        Arrays.sort(arrEdgeVertex);

        return arrEdgeVertex;
    }
}

class EdgeVertex implements Comparable<EdgeVertex> {
    public int weight;
    public String beginVertex;
    public String endVertex;
    public int beginVertexIndex;
    public int endVertexIndex;


    @Override
    public boolean equals(Object o) {
        EdgeVertex edgeVertex = (EdgeVertex) o;
        return this.beginVertex.equals(edgeVertex.beginVertex) && this.endVertex.equals(edgeVertex.endVertex) || this.beginVertex.equals(edgeVertex.endVertex) && this.endVertex.equals(edgeVertex.beginVertex);
    }

    @Override
    public int hashCode() {
        return Objects.hash(beginVertex, endVertex);
    }

    @Override
    public String toString() {
        return String.format("%s<%s,%s>", this.weight, this.beginVertex, this.endVertex);
    }

    @Override
    public int compareTo(EdgeVertex o) {
        return this.weight - o.weight;
    }
}
